home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_glimpse.idb / usr / freeware / src / glimpse-3.0 / compress / defs.h.z / defs.h
C/C++ Source or Header  |  1997-09-09  |  8KB  |  187 lines
  1. /* Copyright (c) 1994 Burra Gopal, Udi Manber.  All Rights Reserved. */
  2.  
  3. /**************************************************************************
  4.  * defs.h:    contains definitions for our static/dictionary based      *
  5.  *        compression scheme that is tailored for very fast search. *
  6.  **************************************************************************/
  7. #ifndef    _DEFS_H_
  8. #define _DEFS_H_
  9.  
  10. #include <sys/types.h>
  11. #include <sys/stat.h>
  12. #include <ctype.h>
  13. #include "glimpse.h"
  14.  
  15. #undef COMP_SUFFIX
  16. #undef DEF_STRING_FILE
  17. #undef DEF_HASH_FILE
  18. #undef DEF_FREQ_FILE
  19. #undef SIGNATURE_LEN
  20.  
  21. #define MIN_WORD_LEN        1        /* smaller words are not indexed: heuristics like special_texts etc. must be used: verbatim is good enough */
  22. #define HASH_TABLE_SIZE        MAX_64K_HASH
  23. #define SMALL_HASH_TABLE_SIZE    MAX_4K_HASH
  24. #define HASH_ENTRY_SIZE        32         /* hash-file stores: name of len=24, a 5 digit int, a ' ' + a '\n' = 31 bytes + some padding once in a while */
  25. #define DEF_BLOCKSIZE        4096        /* I/O unit size = OS page size */
  26. #define MIN_BLOCKSIZE        512        /* granularity for above and below */
  27. #define HASH_FILE_BLOCKS    (HASH_TABLE_SIZE * HASH_ENTRY_SIZE / MIN_BLOCKSIZE)
  28. #define STRING_FILE_BLOCKS    (HASH_TABLE_SIZE * MAX_WORD_LEN / MIN_BLOCKSIZE)
  29. #define MAX_SPECIAL_CHARS    32        /* Maximum # of special characters used during compress */
  30. #define DEF_SPECIAL_WORDS    32        /* Special words for which 1B codes are reserved */
  31.  
  32. #define COMP_ATLEAST        10        /* At least 10% compression is needed */
  33. #define COMP_SUFFIX        ".CZ"        /* Common suffix used for all compressed files: IT INCLUDES THE '.' !!! */
  34. #define DEF_INDEX_FILE        INDEX_FILE    /* same as glimpse's */
  35. #define DEF_STRING_FILE        ".glimpse_uncompress"
  36. #define DEF_HASH_FILE        ".glimpse_compress"
  37. #define DEF_FREQ_FILE        ".glimpse_quick"
  38. #define DEF_THRESHOLD        16        /* 256? default for min bytes to be coverd before storing in hash table */
  39. #define MAX_THRESHOLD        65535        /* MAX_WORDS*MAX_THRESHOLD must be < 2**32 - 1 = maxoffset = maxdiskspace = integer */
  40. #define MAX_LSB            254        /* 256 - |{'\0', '\n'}| */
  41. #define DEF_MAX_WORDS        (MAX_LSB*MAX_LSB)
  42.  
  43. #define SAMPLE_SIZE        8192        /* amount of data read to determine file-type: NOT CALLED FOR STDIN! */
  44. #define SIGNATURE_LEN        16        /* to avoid calling strlen: including \0! */
  45.  
  46. typedef struct _hash_entry {
  47.     struct _hash_entry *next;
  48.     char *word;                /* string itself */
  49.     union {
  50.         int    offset;            /* offset into the dictionary file: used only while building compress's dict from glimpse's dict */
  51.         struct {
  52.             short    freq;        /* number of times the word occurs -- provided it is in the dictionary */
  53.             short    index;        /* index into the string table */
  54.         } attribute;            /* once freq > THRESHOLD, its just an index into the string table: used only while compressing a file */
  55.     } val;
  56. } hash_entry;
  57.  
  58. /*
  59.  * The total number of special characters (1..4) CANNOT exceed MAX_SPECIAL_CHARS.
  60.  * The arrangement is as follows:
  61.  * 1. SPECIAL_TEXTS
  62.  * 2. SPECIAL_SEPARATORS
  63.  * 3. SPECIAL_DELIMITERS
  64.  * 4. VERBATIM
  65.  * 5. SPECIAL_WORDS
  66.  * Any rearrangement of these can be done provided the BEGIN/END values
  67.  * are defined properly: the NUMs remain the same.
  68.  */
  69.  
  70. #define BEGIN_SPECIAL_CHARS    1        /* character 0 is never a part of any code */
  71. #define END_SPECIAL_CHARS    30        /* Not including begin/end verbatim */
  72.  
  73. /* Special delimiters are text-sequences which can come after a word instead of a blank: this is a subset of the above with '\n' and '\t' */
  74. #define EASY_NUM_SPECIAL_DELIMITERS    8    /* numbered from 1 .. 8 */
  75. #define HARD_NUM_SPECIAL_DELIMITERS    9    /* extra: a special kind of newline */
  76. #define SPECIAL_DELIMITERS        { '.', ',', ':', '-', ';', '!', '"', '\'', '\n'}
  77. #define BEGIN_SPECIAL_DELIMITERS    BEGIN_SPECIAL_CHARS
  78. #define EASY_END_SPECIAL_DELIMITERS    9
  79. #define HARD_END_SPECIAL_DELIMITERS    10
  80.  
  81. /* Special separators are things that can separate two words: they are 2blanks, 2tabs or 2newlines */
  82. #define NUM_SEPARATORS        7        /* numbered from 10 .. 16 */
  83. #define NEWLINE            '\n'         /* = HARD_END_SPECIAL_DELIMITERS --> carefully chosen so that this is TRUE !!!! Speeds up searches */
  84. #define NOTBLANK        (NEWLINE + 1)    /* acts like unputc(' ') if char after a word != blk OR sp-delims */
  85. #define BLANK            (NOTBLANK + 1)
  86. #define TAB            (NOTBLANK + 2)
  87. #define TWOBLANKS        (NOTBLANK + 3)    /* Beginning of a sentence */
  88. #define TWOTABS            (NOTBLANK + 4)    /* Indentation */
  89. #define TWONEWLINES        (NOTBLANK + 5)    /* Beginning of a paragraph */
  90. #define BEGIN_SEPARATORS    10
  91. #define END_SEPARATORS        17
  92.  
  93. /*
  94.  * An alternate way would be to have a code for BLANK and NBLANKS, TAB and NTABS, and, NEWLINE and NNEWLINES:
  95.  * in each of these cases, the byte occuring immediately next would determine the number of BLANKS/TABS/NEWLINES.
  96.  * Though this works for a general number of cases, it needs two bytes of encoding: which makes us
  97.  * wonder whether those cases occur commonly enough to waste two bytes to encode two blanks (common).
  98.  * The present encoding guarantees 50% compression for any sequence of separators anyway, and is much simpler.
  99.  */
  100.  
  101. /* Special texts are text-sequences which have a 1 byte codes associated with them: these appear first among the special things */
  102. #define NUM_SPECIAL_TEXTS    13        /* numbered from 17 .. 29 */
  103. #define SPECIAL_TEXTS        { '.', ',', ':', '-', ';', '!', '"', '\'', '#', '$', '%', '(', ')'}    /* Could have used ?, @ and & too */
  104. #define BEGIN_SPECIAL_TEXTS    17
  105. #define END_SPECIAL_TEXTS    30
  106.  
  107. /* Characters for literal text */
  108. #define BEGIN_VERBATIM        30
  109. #define END_VERBATIM        31
  110. #define EASY_ONE_VERBATIM    EASY_END_SPECIAL_DELIMITERS
  111. #define HARD_ONE_VERBATIM    BEGIN_VERBATIM    /* Is not an ascii char since ascii is 32.. */
  112.  
  113. /* BEGIN and END SPECIAL_WORDS are variables */
  114.  
  115. #if    0
  116. /* THIS WON'T REALLY HELP SINCE SOURCE CODE RARELY HAS COMMON WORDS: KEYWORDS ARE VERY SMALL SO THEY HARDLY GIVE ANY COMPRESSION */
  117. char special_program_chars[] = { '.', ',', ':', '-', '!', ';', '?', '+', '/', '\'', '"', '~', '`', '&', '@', '#', '$', '%', '^', '*', '=', '(', ')', '{', '}', '[', ']', '_', '|', '\\', '<', '>' };
  118. #endif    /*0*/
  119.  
  120. /*
  121.  * Common exported functions.
  122.  */
  123.  
  124. unsigned short encode_index();
  125. unsigned short decode_index();
  126. unsigned int mygetc();
  127. int is_little_endian();
  128. int build_string();
  129. int build_hash();
  130. int dump_hash();
  131. int dump_string();
  132. int get_word_from_offset();
  133. int dump_and_free_string_hash();
  134. hash_entry *insert_hash();
  135. hash_entry *get_hash();
  136. int hash_it();
  137.  
  138. /*
  139.  * The beauty of this allocation scheme is that "free" does not need to be implemented!
  140.  * The total memory occupied by both the string and hash tables is appx 1.5 MB
  141.  */
  142.  
  143. #define hashfree(h)    if (usemalloc) free(e);
  144.  
  145. #define hashalloc(e) \
  146. {\
  147.     if (usemalloc) (e) = (hash_entry *)malloc(sizeof(hash_entry));\
  148.     else {\
  149.         if (free_hash == NULL) free_hash = (hash_entry *)malloc(sizeof(hash_entry) * DEF_MAX_WORDS);\
  150.         if (free_hash == NULL) (e) = NULL;\
  151.         else (e) = ((next_free_hash >= DEF_MAX_WORDS) ? (NULL) : (&(free_hash[next_free_hash ++])));\
  152.     }\
  153.     if ((e) == NULL) {fprintf(stderr, "Out of memory in cast-hash-table!\n"); exit(2); }\
  154. }
  155.  
  156. #define strfree(s)    if (usemalloc) free(s);
  157.  
  158. /* called ONLY in the build procedure in which we can afford to be slow and do an strcpy since sizes of words are not determined: hardcoded in build_hash() */
  159. #define stralloc(s, len) \
  160. {\
  161.     if (usemalloc) (s) = (char *)malloc(len);\
  162.     else {\
  163.         if (free_str == NULL) free_str = (char *)malloc(AVG_WORD_LEN * DEF_MAX_WORDS);\
  164.         if (free_str == NULL) (s) = NULL;\
  165.         else (s) = ((next_free_str >= AVG_WORD_LEN * DEF_MAX_WORDS) ? (NULL) : (&(free_str[next_free_str]))); next_free_str += (len);\
  166.     }\
  167.     if ((s) == NULL) {fprintf(stderr, "Out of memory in cast-string-table!\n"); exit(2); }\
  168. }
  169.  
  170. /* There is no equivalent strtablealloc since it is hardcoded into build_string and is not used anywhere else */
  171.  
  172. /* Some flags corr. to user options: avoid global variables for options, pass flags as parameters */
  173. #define TC_EASYSEARCH    0x1
  174. #define TC_UNTILNEWLINE    0x2
  175. #define TC_REMOVE    0x4
  176. #define TC_OVERWRITE    0x8
  177. #define TC_RECURSIVE    0x10
  178. #define TC_ERRORMSGS    0x20
  179. #define TC_SILENT    0x40
  180. #define TC_NOPROMPT    0x80
  181. #define TC_FILENAMESONSTDIN 0x100
  182.  
  183. #define CAST_VERSION    "1.0"
  184. #define CAST_DATE    "1994"
  185.  
  186. #endif    /*_DEFS_H_*/
  187.